Tri indirect ou Tri par index

Important : le tri indirect n'est pas un algorithme de tri. C'est une technique d'écriture qui s'applique par-dessus un tri existant (Heap Sort, Insertion Sort, etc.). L'idée : au lieu de déplacer les objets eux-mêmes, on trie un tableau d'indices qui pointent vers eux.

Pourquoi l'utiliser ?

Quand les objets à trier sont volumineux ou complexes (ex. des objets Personne avec 20 champs), les déplacer en mémoire à chaque échange est coûteux. Avec le tri indirect :

• Le tableau original ne bouge jamais.
• On ne trie qu'un tableau d'entiers (les indices) → les échanges sont rapides.
• On peut avoir plusieurs ordres de tri différents sur les mêmes données sans les copier.

Principe :

1. Créer un tableau tabIndex initialisé à [0, 1, 2, 3, 4, ...].
2. Trier tabIndex en comparant les éléments du tableau original via ces indices.
3. Accéder aux données dans l'ordre trié via tabOriginal[tabIndex[i]].

Le tableau original n'est jamais modifié.

Exemple :

Tableau de départ tabChar :

Index	0	1	2	3	4
Valeur	'b'	'd'	'c'	'a'	'e'

tabIndex au départ : [0, 1, 2, 3, 4] (ordre naturel)

On trie tabIndex en comparant tabChar[tabIndex[i]] :

• 'a' est en position 3 → le plus petit → va en premier
• 'b' est en position 0 → deuxième
• 'c' est en position 2 → troisième
• 'd' est en position 1 → quatrième
• 'e' est en position 4 → dernier

tabIndex après tri : [3, 0, 2, 1, 4]

Pour lire dans l'ordre trié : tabChar[3]='a', tabChar[0]='b', tabChar[2]='c', tabChar[1]='d', tabChar[4]='e' ✓

tabChar original : inchangé → ['b', 'd', 'c', 'a', 'e']

Code Java :

char[] tabChar = {'b', 'd', 'c', 'a', 'e'};
int[] tabIndex = {0, 1, 2, 3, 4};

// --- Tri à bulles sur tabIndex ---
// On compare les caractères du tableau original via les indices
// On ne touche JAMAIS à tabChar — on échange uniquement des entiers dans tabIndex
int n = tabIndex.length;
for (int i = 0; i < n - 1; i++) {
    for (int j = 0; j < n - 1 - i; j++) {
        // Comparer les caractères pointés par les deux indices
        if (tabChar[tabIndex[j]] > tabChar[tabIndex[j + 1]]) {
            // Échanger les indices (pas les caractères !)
            int temp = tabIndex[j];
            tabIndex[j] = tabIndex[j + 1];
            tabIndex[j + 1] = temp;
        }
    }
}

// Lecture dans l'ordre trié via les indices
for (int i = 0; i < n; i++) {
    System.out.print(tabChar[tabIndex[i]] + " "); // a b c d e
}

Déroulement pas à pas du tri à bulles sur tabIndex

Tableau original tabChar (ne change jamais) :

Index	0	1	2	3	4
Valeur	'b'	'd'	'c'	'a'	'e'

tabIndex au départ : [0, 1, 2, 3, 4]

Passe 1 (le plus grand remonte à la fin) :

Comparaison	tabChar[tabIndex[j]] vs tabChar[tabIndex[j+1]]	Échange ?	tabIndex résultant
j=0	tabChar[0]='b' vs tabChar[1]='d'	Non	[0, 1, 2, 3, 4]
j=1	tabChar[1]='d' vs tabChar[2]='c'	Oui (d > c)	[0, 2, 1, 3, 4]
j=2	tabChar[1]='d' vs tabChar[3]='a'	Oui (d > a)	[0, 2, 3, 1, 4]
j=3	tabChar[1]='d' vs tabChar[4]='e'	Non	[0, 2, 3, 1, 4]

→ Après passe 1 : tabIndex = [0, 2, 3, 1, 4] (l'indice de 'e' est déjà en place)

Passe 2 :

Comparaison	tabChar[tabIndex[j]] vs tabChar[tabIndex[j+1]]	Échange ?	tabIndex résultant
j=0	tabChar[0]='b' vs tabChar[2]='c'	Non	[0, 2, 3, 1, 4]
j=1	tabChar[2]='c' vs tabChar[3]='a'	Oui (c > a)	[0, 3, 2, 1, 4]
j=2	tabChar[2]='c' vs tabChar[1]='d'	Non	[0, 3, 2, 1, 4]

→ Après passe 2 : tabIndex = [0, 3, 2, 1, 4]

Passe 3 :

Comparaison	Échange ?	tabIndex résultant
j=0 : 'b' vs 'a'	Oui	[3, 0, 2, 1, 4]
j=1 : 'b' vs 'c'	Non	[3, 0, 2, 1, 4]

→ Après passe 3 : tabIndex = [3, 0, 2, 1, 4]

Passe 4 :

Comparaison	Échange ?	tabIndex résultant
j=0 : 'a' vs 'b'	Non	[3, 0, 2, 1, 4]

→ tabIndex final : [3, 0, 2, 1, 4] ✓

Lecture du résultat :

• tabChar[3] = 'a'
• tabChar[0] = 'b'
• tabChar[2] = 'c'
• tabChar[1] = 'd'
• tabChar[4] = 'e'

tabChar original : ['b', 'd', 'c', 'a', 'e'] → inchangé ✓

Complexité :

• Dépend du tri appliqué sur tabIndex (ex. O(n log n) avec Heap Sort).
• Mémoire : O(n) pour le tableau d'indices supplémentaire.

À noter :

• Le tableau original n'est jamais modifié ni copié.
• Très utilisé avec des objets complexes (personnes, fichiers, enregistrements).
• C'est le même mécanisme qu'utilisent les index de bases de données.